1. Field of the Invention
This invention relates to pipelined image processing systems, and more particularly relates to a parallel pipeline system of image processing elements, which are configurable in sets and partially configurable from set to set within an image processing subassembly, for computational efficiency and economy of memory and bus capacity.
2. Description of the Prior Art
The following United States Patents and other publications are representative of the prior art:
U.S. Pat. No. 3,805,035, Serra, J., DEVICE FOR THE LOGICAL ANALYSIS OF TEXTURES, Apr. 16, 1974, shows image conversions in accordance with predetermined Boolean logical laws.
U.S. Pat. No. 4,395,699, Sternberg, METHOD AND APPARATUS FOR PATTERN RECOGNITION AND DETECTION, July 26, 1983, shows the use of table look-up in a pattern recognition and detection system employing at least one neighborhood transformation stage. The table look-up is not used to control Boolean transformations of the image, but rather is used in a character recognition mode to determine whether neighboring pixels are configured in a preselected pattern.
U.S. Pat. No. 4,395,700, McCubbrey et al, IMAGE ANALYZER WITH VARIABLE LINE STORAGE, July 26, 1983, shows a system for analyzing images, in which each neighborhood transformation stage includes a processor portion for analyzing windows of neighboring pixel values and provides a transformation output as a function of the pixel values contained in the window.
U.S. Pat. No. 4,484,346, Sternberg et al, NEIGHBORHOOD TRANSFORMATION LOGIC CIRCUITRY FOR AN IMAGE ANALYZER SYSTEM, Nov. 20, 1984, shows a system for analyzing images represented by a serial stream of digital pixel signals constituting an image. The system includes a pipeline of substantially identical neighborhood transformation stages. Each stage sequentially provides a window of neighboring pixels to the processor for analysis.
U.S. Pat. No. 4,490,848, Beall et al, METHOD AND APPARATUS FOR SORTING CORNER POINTS IN A VISUAL IMAGE PROCESSING SYSTEM, Dec. 25, 1984, shows an image processor which processes extracted features, using a first microprocessor to control video data processing functions, using a second microprocessor to control subsequent more complex image data processing functions, and using a third microprocessor as the main CPU communicating via a common bus.
(application Ser. No. 06/626,552, filed June 29, 1984), Mandeville, METHOD FOR OPTICAL INSPECTION ANALYSIS OF INTEGRATED CIRCUITS, shows, in an automatic inspection system for intricate devices, a finite-length serial pipeline configuration for processing images.
U.S. patents which provide cumulative pertinent prior art include:
U.S. Pat. No. 4,174,514, Sternberg, PARALLEL PARTITIONED SERIAL NEIGHBORHOOD PROCESSORS, Nov. 13, 1979, shows an image processor technique for operating across boundaries of image segments.
U.S. Pat. No. 4,395,698, Sternberg et al, NEIGHBORHOOD TRANSFORMATION LOGIC CIRCUITRY FOR AN IMAGE ANALYZER SYSTEM, July 16, 1983, shows an image processing system for two-dimensional or three-dimensional image analysis.
U.S. Pat. No. 4,441,207, Lougheed et al, DESIGN RULE CHECKING USING SERIAL NEIGHBORHOOD PROCESSORS, Apr. 3, 1984, shows an image processing system for checking superimposed integrated circuit masks.
U.S. Pat. No. 4,464,788, Sternberg et al, DYNAMIC DATA CORRECTION GENERATOR FOR AN IMAGE ANALYZER SYSTEM, Aug. 7, 1984, shows an adjustment technique for correcting "wrap-around" ambiguity interval.
U.S. Pat. No. 4,484,349, McCubbrey, PARALLEL PIPELINE IMAGE PROCESSOR, Nov. 20, 1984, shows a technique for image processing in a segmented fashion in which pixels lying at segment edges are transferred for processing by another segment and are also retained in output buffers, so that each stage contains all the pixels needed for processing.
U.S. Pat. No. 3,970,993 Finnila, COOPERATIVE-WORD LINEAR ARRAY PARALLEL PROCESSOR, July 20, 1976, shows an array parallel processor with associative addressing. Since words are content-addressed, simple logic can provide self-repair. Finnila may run a test program through the cells, bypassing some cells under program control. Each cell has a plurality of flag positions, and flag data may be processed or transferred. Finnila can bypass a cell, but does not have any reconfiguration capability.
U.S. Pat. No. 3,603,934, Heath, Jr., DATA PROCESSING SYSTEM CAPABLE OF OPERATION DESPITE A MALFUNCTION, Sept. 7, 1971, shows a computer system with redundancy and fault bypass, using multiple passes through the good units if required. The Heath fault bypass might be considered a form of reconfiguration, but it does not provide a reconfigurable image processing system.
U.S. Pat. No. 3,553,654, Crane, FAULT ISOLATION ARRANGEMENT FOR DISTRIBUTED LOGIC MEMORIES, Jan. 5, 1971, shows a fault isolation system for a distributed logic memory. Fault detection controls fault bypass. This is not a reconfigurable image processing system.
U.S. Pat. No. 3,681,578, Stevens, FAULT LOCATION AND RECONFIGURATION IN REDUNDANT DATA PROCESSORS, Aug. 1, 1971, provides a majority voting circuit. This is not a reconfigurable image processor.
U.S. Pat. No. 3,356,837, Raymond, BINARY DATA INFORMATION HANDLING SYSTEMS, Dec. 5, 1967, provides a majority voting circuit. This is not a reconfigurable image processor.
U.S. Pat. No. 3,226,569, FAILURE DETECTION CIRCUITS FOR REDUNDANT SYSTEMS, Dec. 28, 1965, provides a majority voting circuit. This is not a reconfigurable image processor.
U.S. Pat. No. 3,660,646, Minero et al, CHECKING BY PSEUDODUPLICATION, May 2, 1972, provides error detection by pseudoduplication, performing the same operation twice, with different data paths, and comparing the result. While this might be considered a "reconfiguration" in the broad dictionary sense, it does not provide a reconfigurable image processor.
U.S. Pat. No. 4,398,248, Hsia et al, ADAPTIVE WSI/MNOS SOLID STATE MEMORY SYSTEM, Aug. 9, 1983, shows error detection controlled fault bypass to redundant circuitry. This is not a reconfigurable image processor.
U.S. Pat. No. 3,665,418, Bouricius et al, STATUS SWITCHING IN AN AUTOMATICALLY REPAIRED COMPUTER, May 23, 1972, shows error detection controlled fault bypass to redundant circuitry. This is not a reconfigurable image processor.
U.S. Pat. No. 3,419,849, Anderson et al, MODULAR COMPUTER SYSTEM, Dec. 31, 1968, shows error detection controlled fault bypass to redundant circuitry. This is not a reconfigurable image processor.
SU 0543941, Tsiramua et al, Jan. 1977 (USSR Author's Certificate) shows a fault-tolerant system which reallocates functions via a function distributor. This is not a reconfigurable image processor.
JA 54-30383, BACK-UP SYSTEM OF DIGITAL PROCESS CONTROLLING APPARATUS, March 1979, shows error detection controlled fault bypass to redundant circuitry. This is not a reconfigurable image processor.
Publications are:
E. J. Lerner, "Parallel Processing Gets Down To Business," High Technology, Jul 1985, pp. 9-14. Lerner shows a variety of styles and uses of parallel processors.
J. R. Mandeville, "Novel Method for Analysis of Printed Circuit Inmages, IBM J. Res. Develop., Vol. 29 No. 1, January 1985, pp. 73-86. Mandeville shows, in an automatic inspection system for intricate devices, a finite-length serial pipeline configuration for processing images.
R. M. Lougheed, D. L. McCubbrey, "The Cytocomputer: A Practical Pipelined Image Processor," Proc. 7'th Annual International Symposium on Computer Architecture, May 1980, shows a pipelined image processor.
Other publications, considered cumulative, are:
D. Svetkoff, J. Candlish, P. VanAtta, "High Resolution Imaging for Visual Inspection of Multi-Layer Thick-Film Circuits," RI/SME Conference on Applied Machine Vision, Memphis, Tennessee, February 1983, shows an image processor using a gray-scale algorithm to locate and classify flaws.
U. Montanari "Continuous Skeletons From Digitized Images," Journal of the Association for Computing Machinery, Vol. 16, No. 4, October 1969, pp. 534-549, shows an image processing technique involving skeletonizing of digitized images for feature extraction.
R. Stefanelli, A. Rosenfeld, "Some Parallel Thinning Algorithms for Digital Pictures," Journal of the Association for Computing Machinery, Vol. 18, No. 2, April 1971, pp. 255-264, shows a thinning technique operating on an image processor.
S. R. Sternberg, "Biomedical Image Processing," IEEE Computer, January 1983, pp. 22-28, shows an image processing technique involving erosion and dilation of images for feature extraction.
S. R. Sternberg, "Language and Architecture for Parallel Image Processing." in PATTERN RECOGNITION IN PRACTICE, E. S. Gelsema and L. N. Kanal, eds., North Holland Publishing Co., 1980, shows techniques for image processing in an array processor.
K. S. Fu, "Pattern Recognition for Automatic Visual Inspection," IEEE COMPUTER, December 1982, shows techniques for image processing.
R. M. Lougheed, D. L. McCubbrey, S. R. Sternberg, "Cytocomputers: Architectures for Parallel Image Processing," Proc. IEEE Workshop on Picture Data Description and Management, August 1980, pp. 281-286, shows architecture and operation techniques for image processors.
M. A. Hegyi, R. W. Kelley, D. L. McCubbrey, C. B. Morningstar, "Computer Algorithms for Visually Inspecting Thick Film Circuits," Environmental Research Institute of Michigan, shows operation techniques for image processing.
Hopkins, Jr., et al, "FTMP - A Highly Fault-Tolerant Multiprocessor for Aircraft," Proceedings of the IEEE, Vol. 66, No. 10, October 1978, pp. 1221-1239, shows error detection controlled fault bypass to redundant circuitry. This is not a reconfigurable image processor.
J. Losq, "A Highly Efficient Redundancy Scheme: Self-Purging Redundancy," IEEE Transactions on Computers, Vol. C-25, No. 6, June 1976, pp. 569-578, shows error detection controlled fault bypass to redundant circuitry. This is not a reconfigurable image processor.
C. V. Ramamoorthy et al, "Reliability Analysis of Systems with Concurrent Error Detection," IEEE Transactions on Computers, Vol. C-24, No. 9, September 1975, pp. 868-878, shows error detection controlled fault bypass to redundant circuitry. This is not a reconfigurable image processor.
A. Bautista et al, "An Architectural Design for Simultaneous Microdiagnostic," Microprocessing and Microprogramming 9, No. 1 (Jan. 1982), pp. 27-37, shows normal program execution simultaneous with diagnostics program execution.
D. R. Harper et al, "Concurrent Memory Diagnostics," IBM Technical Disclosure Bulletin, Vol. 14, No. 8, January 1972, pp. 2366-2367, shows normal program execution simultaneous with diagnostics program execution.
S. R. Sternberg, "Industrial Computer Vision by Mathematical Morphology," Conf. Proc. 13th Intl. Symposium on Industrial Robots & Robots 7, Chicago, Ill., 1983, Apr. 17-21, pp. 17-14 to 17-35, shows an image processor technique for computer vision. There is no reconfigurability shown.
S. R. Sternberg, "Parallel Processing in Machine Vision," Proc. of the Robotic Intelligence and Productivity Conf., Detroit, MI., Nov. 1983, pp. 35-44, shows the use of parallel image processing in machine vision.
S. R. Sternberg, "Parallel Architectures for Image Processing," Real-Time/Parallel Computing. Image Analysis Proc. of part of the JA-US Seminar, Tokyo, JA, Oct. Nov. 1978, pp. 347-359, surveys parallel architectures and operating techniques for image processing, but without the reconfigurability feature.
S. R. Sternberg, "Architectures for Neighborhood Processing," IEEE Comp. Soc. Conf. on Pattern Recognition and Image Processing, Dallas, TX., Aug. 3-5, 1981, pp. 374-380, surveys architectures for neighborhood processing, including serial array processors of several types. One type, the parallel partitioned serial array processor, ". . . takes the form of two or more serial array processors adapted to simultaneously process separate, contiguous segments of a data matrix . . . " so the ". . . two serial array processors . . . equally divide the task of transforming a single data matrix."
Sternberg and Sternberg, "Industrial Inspection by Morphological Virtual Gauging," IEEE Computer Soc. Workshop on Computer Architecture for Pattern Analysis & Image Mangmt. 1983, pp. 237-247, show the use of image processing for "virtual gauging," where the shape of the gauge is determined using software. There is no reconfigurability feature.
S. R. Sternberg, "Cellular Computers and Biomedical Image Processing," Publ. by Springer-Verlang, Berlin, West GER & New York, 1982, pp. 294-319, shows the use of image processing in biomedicine, using image algebra in a pipeline image processor for body cell analysis. There is no reconfigurability feature.
Mudge et al, "Cellular Image Processing Techniques for VLSI Circuit Layout Validation and Routing," 19th Design Automation Conference, June 1982, Paper 32.2, pp. 537-543, shows the architecture of a pipelines cellular image processor. "Shift registers within each stage stores two contiguous scan lines while window registers hold the nine neighborhood pixels which constitute the 3.times.3 window . . . performs a preprogrammed transformation . . . [O]perations which do not involve the states of a pixel's neighbors . . . are performed in a separate point-by-point logic section to simplify the neighborhood logic circuit . . . " (p. 538). There is no reconfigurability feature.
The prior art shows a variety of pipeline processors, and shows that such pipeline image processors are advantageous in that many computations are done simultaneously without constant memory accessing of intermediate results. The term "image" is used in the broadest sense, covering spatially or temporally related information. The prior art however does not teach nor suggest a configurable network system architecture to carry out high speed pipelined processing of very large numbers of window images, with efficient use of hardware, by using a host computer to reconfigure a limited set of hardware to set up the system as an efficient image processing network for the particular job.